package com.dyz.leetcode;

public class CountBits338 {
    public int[] countBits(int n) {
        //方法以调用工具类 遍历统计每个数二进制数对应一的个数即可
        int [] res = new int[n+1];
        for (int i=0; i<=n; i++){
            res[i] = Integer.bitCount(i);
        }
        return res;
    }
    public int[] countBits1(int n) {
        //方案二 动态规划  找到地推方程 dp[i] = dp[i&(i-1)] +1
        //验证 6（110） = 4（100）+2（10）
        //根据n&(n-1)实际上是把n的二进制数中最低的1给去掉了，这里6的二进制110相当于把第二为1给去掉了，而4的二进制100刚好等于2的二进制10+1得到的，
        //故推出动态规划递推式dp[i] = dp[i&(i-1)]+1
        int[] dp = new int[n+1];
        for (int i=1; i<=n;i++){
            dp[i] = dp[i&(i-1)]+1;
        }
        return dp;

    }
}
